import java.util.*;


interface Sorter {
	void sort( Comparable [ ] a );
}


class QuickSort implements Sorter {

	public void sort( Comparable [ ] a ) {
        quicksort( a, 0, a.length - 1 );
    }

    private static final int CUTOFF = 10;

    private void quicksort( Comparable [ ] a, int low, int high )
    {
        if( low + CUTOFF > high )
            insertionSort( a, low, high );
        else {
                // Sort low, middle, high
            int middle = ( low + high ) / 2;
            if( a[ middle ].compareTo( a[ low ] ) < 0 )
                swapReferences( a, low, middle );
            if( a[ high ].compareTo( a[ low ] ) < 0 )
                swapReferences( a, low, high );
            if( a[ high ].compareTo( a[ middle ] ) < 0 )
                swapReferences( a, middle, high );

                // Place pivot at position high - 1
            swapReferences( a, middle, high - 1 );
            Comparable pivot = a[ high - 1 ];

                // Begin partitioning
            int i, j;
            for( i = low, j = high - 1; ; )
            {
                while( a[ ++i ].compareTo( pivot ) < 0 )
                    ;
                while( pivot.compareTo( a[ --j ] ) < 0 )
                    ;
                if( i >= j )
                    break;
                swapReferences( a, i, j );
            }

                // Restore pivot
            swapReferences( a, i, high - 1 );

            quicksort( a, low, i - 1 );    // Sort small elements
            quicksort( a, i + 1, high );   // Sort large elements
        }
    }

    public void swapReferences( Object [ ] a, int index1, int index2 ) {
        Object tmp = a[ index1 ];
        a[ index1 ] = a[ index2 ];
        a[ index2 ] = tmp;
    }

	private void insertionSort( Comparable [ ] a, int low, int high ) {
        for( int p = low + 1; p <= high; p++ ) {
            Comparable tmp = a[ p ];
            int j;

            for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }
}


class MergeSort implements Sorter {
	public void sort( Comparable [ ] a ) {
		Comparable [ ] tmp = new Comparable[ a.length ];
		sort( a, tmp, 0, a.length - 1 );
	}

	void sort( Comparable [ ] a, Comparable [ ] tmp, int left, int right) {
		if ( left < right ) {
			int center = ( left + right ) / 2;
			sort( a, tmp, left, center );
			sort( a, tmp, center + 1, right );
			merge( a, tmp, left, center, center + 1, right );
		}
	}

	void merge( Comparable [ ] a, Comparable [ ] tmp,
				int leftStart, int leftEnd,
				int rightStart, int rightEnd) {

		int leftPos = leftStart;
		int rightPos = rightStart;
		int tmpPos = leftStart;

		while ( leftPos <= leftEnd && rightPos <= rightEnd ) {
			if ( a[ leftPos ].compareTo( a[ rightPos ] ) < 0 ) {
				tmp[ tmpPos++ ] = a[ leftPos++ ];
			}
			else {
				tmp[ tmpPos++ ] = a[ rightPos++ ];
			}
		}

		while ( leftPos <= leftEnd ) {
			tmp[ tmpPos++ ] = a[ leftPos++ ];
		}

		while ( rightPos <= rightEnd ) {
			tmp[ tmpPos++ ] = a[ rightPos++ ];
		}

		for ( int i = leftStart; i <= rightEnd; ++i ) {
			a[ i ] = tmp[ i ];
		}
	}
}


class InsertionSort implements Sorter {
    public void sort( Comparable [ ] a ) {

        for( int p = 1; p < a.length; p++ ) {
            Comparable tmp = a[ p ];
			
            int j;
            for(j = p ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- ) {
                a[ j ] = a[ j - 1 ];
			}

            a[ j ] = tmp;
        }
    }
}


class SelectionSort implements Sorter {
    public void sort (Comparable[] a) {

		for (int i = 0; i < a.length-1; i++) {
	    	int min = i;

	    	for (int j = i+1; j < a.length; j++) {

				if (a[j].compareTo(a[min]) < 0) {
		    		min = j;
				}
			}

	    	Comparable tmp = a[min];
	    	a[min] = a[i];
	    	a[i] = tmp;
		}
    }
}


public class Sort {

	static void runSort(Sorter sorter, String sortName) {
		System.out.println(sortName);

		for (int SIZE = 100; SIZE < 1000000; SIZE *= 2) {
	    	long start, end;
	    	long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;
	    	Comparable [ ] a = new Comparable [ SIZE ];

			// sorted input
	    	for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( i );
			}
	    	start = System.currentTimeMillis();
	    	sorter.sort( a );
	    	end = System.currentTimeMillis();
	    	elapsed1 = end - start;

			// reverse sorted input
		    for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( SIZE - i );
			}
	    	start = System.currentTimeMillis();
	    	sorter.sort( a );
	    	end = System.currentTimeMillis();
	    	elapsed2 = end - start;

			// random input
		    Random r = new Random();
		    for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( r.nextInt(SIZE) );
			}
		    start = System.currentTimeMillis();
		    sorter.sort( a );
	    	end = System.currentTimeMillis();
		    elapsed3 = end - start;

		    System.out.println("size: " + SIZE + 
							   "\tsorted: " + elapsed1 + 
						       "\treverse: " + elapsed2 + 
							   "\trandom: " + elapsed3);
		}
	}

    public static void main (String[] args) {
		runSort(new QuickSort(), "Quick Sort");
		runSort(new MergeSort(), "Merge Sort");
		runSort(new InsertionSort(), "Insertion Sort");
		runSort(new SelectionSort(), "Selection Sort");
    }

}